1. Technical Field
The invention relates generally to computer graphics systems, and, particularly, to computer graphics systems that provide real-time interactive and/or scientific visualization of complex geometric models.
2. Description of the Related Art
Traditional computer graphics systems are used to create a model of three-dimensional objects and render the model for display on a two-dimensional display device such as a cathode ray tube or liquid crystal display. Typically, the three-dimensional objects of the model are each represented by a multitude of polygons (or primitives) that approximate the shape of the object. The primitives that define an object are typically defined by coordinates in a local coordinate system. For example, one of the primitives that may be used to define an object is a triangle, which is defined by the coordinates of three vertices in the local coordinate system.
Such polygonal surfaces may be sued for generating pictures and animations, and may also be used in scientific visualization, in geometric computing as well as in medical imaging. More specifically, polygonal surfaces have been used for measuring volumes, for aligning three dimensional scans such as Computed Tomography or Magnetic Resonance scans, or for finite element applications. IBM Visualization Data Explorer is an example of software that generates and visualizes polygonal surfaces.
The rendering of a polygonal surfaces is divided into two stages: geometry processing and rasterization. Geometry processing typically includes a modeling transformation, lighting calculations, a viewing transformation, a clipping function, and viewport mapping. The modeling transformation transforms the primitives from the local coordinate system to a world coordinate system. The lighting calculations evaluate an illumination model at various locations: once per primitive for constant shading, once per vertex for Gouraud shading, or once per pixel for Phong shading. The viewing transformation transforms the primitives in world coordinates to a 3D screen coordinate system (sometimes referred to as the normalized projection coordinate system). The clipping function determines the primitives (or portions of the primitives) that are within the viewing frustrum. And viewport mapping maps the coordinates of the clipped primitives to the normalized device coordinate system (sometimes referred to as the 2D device coordinate system).
Rasterization is the process which converts the description of the clipped primitives generated during geometry processing into pixels for display. A typical primitive, as shown in FIG. 1A, is a triangle T1. Other area or surface primitives conventionally are converted into one or more triangles prior to rasterization. Consequently, the conventional rasterization process need only to handle triangles. The triangle T1 is represented by the (x, y, z) coordinates at each of its vertices. The (x, y) coordinates of a vertex tell its location in the plane of the display. The z coordinate tells how far the vertex is from the selected view point of the three-dimensional model. Rasterization is typically divided into three tasks: scan conversion, shading, and visibility determination.
Scan conversion utilizes the (x, y) coordinates of the vertices of each triangle to compute a set of pixels S which is covered by the triangle. Shading computes the colors of the set of pixels S covered by each triangle. There are numerous schemes for computing colors, some of which involve computationally intensive techniques such as texture mapping. Shading typically utilizes the lighting calculations described above with respect to geometric processing.
Visibility determination utilizes the z coordinate of each triangle to compute the set of pixels Sv (a subset of S) which are xe2x80x9cvisiblexe2x80x9d for the triangle. The set Sv will differ from the set S if any of the pixels in set S are covered by previously rasterized triangles whose z values are closer to the selected view point. Thus, for each triangle in the model, a pixel is xe2x80x9cvisiblexe2x80x9d if it is in the set Sv or xe2x80x9chiddenxe2x80x9d if it is the set S but not in the set Sv. Moreover, a triangle is xe2x80x9call visiblexe2x80x9d if the set Sv is identical to set S, xe2x80x9cpartially hiddenxe2x80x9d if the set Sv is not identical to set S and set Sv is not empty, or xe2x80x9call hiddenxe2x80x9d if set Sv is empty. For example, FIG. 1B shows two triangles, triangle T1 and T2, wherein triangle T1 is partially hidden by triangle T2. Visibility determination is traditionally accomplished using a z-buffer technique. The Z-buffer stores an entry for each pixel that represents the z-value of the visible primitive at the given pixel. The z-value (Znew) of a set of pixels covered by a given triangle is determined through interpolation. For each pixel within the set, Znew at the given pixel is compared to the z-value (Zold) stored as an entry in the Z-buffer corresponding to the given pixel, and the entry Zold is updated with Znew according to results of the compare operation.
Rasterization is completed by writing the colors of the set of visible pixels Sv to an image buffer for display.
As models become more and more complex, traditional rendering techniques are too computationally intensive for many graphics systems and result in degraded performance. For example, it is not rare in medical imaging applications that a surface may contain hundreds of thousands of triangles. In such a case, traditional rendering techniques are not sufficient using current computer hardware and software. In order to solve this problem, several simplification techniques have been developed that construct an approximation of the original surface, and thus reduce the level of detail of the graphical representation of the surface.
An example of such simplification techniques is described Kalvin et al. xe2x80x9cSuperfaces: Polygonal Mesh Simplification with Bounded Errorxe2x80x9d, Computer Graphics and Applications, Vol. 16, No. 3, May 1996, pp.64-77, Cohen et al., xe2x80x9cSimplification Envelopesxe2x80x9d, ACM SIGGRAPH 96, August 1996, Addison Wesley, pp. 119-128, and Ronfard et al., xe2x80x9cFull-Range Approximation of Triangulated Polyhedraxe2x80x9d, Computer Graphics Forum, Vol. 15, 1996, pp.67-76. All three algorithms do not undo any simplification that was previously made.
The simplification technique of Kalvin et al. attempts to merge surface triangles to quasi-planar xe2x80x9csuperfacesxe2x80x9d. Each original triangle is merged with one superface, possibly limited to one single triangle. Each superface is guaranteed to lie within a given distance to the triangles that were merged into the superface. However, because the algorithm does not give priorities to triangles before merging them, the algorithm does not produce economical simplifications for a given amount of processing time. In addition, the algorithm does not preserve the volume of a solid. Finally, the algorithm does not attempt to optimize the aspect ratios of triangles.
The simplification technique of Cohen et al. begins by constructing an envelope around the original surface, whose width corresponds to the maximum distance that is allowed between the simplified surface and the original surface. The envelope does not intersect itself. The surface vertices are then selected as candidates for removal and the hole left by the vertex removal is triangulated. The simplification algorithm ends when no more removal is possible. A verification process verifies that each new triangle is inside the envelope and that it does not intersect other surface triangles. This algorithm is computationally intensive and does not preserve the volume of a solid.
The simplification technique of Ronfard et al. places the edges of the surface in a priority queue, ordered by a key that measures the approximation error after the edge collapse. Until the key exceeds a user specified value, the edge with the highest priority is collapsed. This algorithm is computationally intensive because each time an edge collapse is performed, the simplification error must be re-estimated for each edge that was adjacent to the collapsed edge. Moreover, the technique does not guarantee that the distance between any point of the original surface and the simplified surface and the distance between any point of the simplified surface and the original surface will be less than a user-specified tolerance, but can only guarantee that a factor of this tolerance, depending on the surface geometry, will be respected. Also, the technique does not preserve a volume of a solid.
Moreover, none of the prior art techniques report, for each point of the simplified surface, a useful bound to the error at that point, which is the distance to the original surface at that point. Instead, the prior art techniques report a global error bound which is not directly related to the particular error at that point.
The above-stated problems and related problems of the prior art are solved with the principles of the present invention, surface simplification preserving a solid volume and respecting distance tolerances. Computer systems may be used to generate and display objects represented by triangles defined by coordinates of vertices. The present invention generates coordinates of a simplified vertex based upon coordinates of vertices adjacent to a first vertex and to a second vertex that define an edge of the triangles. First, a set of triangles that are adjacent to the edge is identified, Second, a first volume associated with the set of triangles is calculated. Finally, the coordinates of the simplified vertex are calculated such that a second volume associated with the simplified vertex corresponds to the first volume.
In addition, a technique is presented that generates a second object which is a simplified representation of a first object. The technique begins by identifying first and second vertices that define an edge. The coordinates of a simplified vertex that corresponds to first and second vertices of the edge is determined. Error values and tolerance values are assigned to vertices. First error volumes corresponding to the vertices of a first set of triangles are derived. The first set of triangles share at least one of the first and second vertices of the edge. The first error volumes are based upon the error values assigned to vertices of the first set of triangles. A second set of triangles that share the simplified vertex is identified and partitioned into a set of planar polygons. Second error volumes corresponding to vertices of the set of planar polygons are derived based upon the first error volumes. The second error volumes enclose the first error volumes. Third error volumes corresponding to vertices of the second set of triangles are derived. The third error volumes are based upon the first and second error volumes. The third volumes enclose both the first error volumes and the second error volumes. A tolerance volume corresponding to the simplified vertex is derived. Fianllym, the coordinates of the simplified vertex is stored in memory for subsequent reuse based upon a comparison operation of the third error volume corresponding to the simplified vertex and the tolerance volume.